//#include <iostream>
//#include <string>
//#include <algorithm>
//using namespace std;
//
//string str;
//
//int main()
//{
//	cin >> str;
//	int pos = str.find(".");
//	if (pos != string::npos)
//	{
//		string a = str.substr(0, pos);
//		string b = str.substr(pos + 1);
//
//		while (a.size() > 1 && a[a.size() - 1] == '0')
//			a.pop_back();
//		reverse(a.begin(), a.end());
//
//		reverse(b.begin(), b.end());
//		while (b.size() > 1 && b[b.size() - 1] == '0')
//			b.pop_back();
//
//		cout << a << "." << b << endl;
//
//		return 0;
//	}
//	pos = str.find("/");
//	if (pos != string::npos)
//	{
//		string a = str.substr(0, pos);
//		string b = str.substr(pos + 1);
//
//		while (a.size() > 1 && a[a.size() - 1] == '0')
//			a.pop_back();
//		while (b.size() > 1 && b[b.size() - 1] == '0')
//			b.pop_back();
//
//		reverse(a.begin(), a.end());
//		reverse(b.begin(), b.end());
//
//		cout << a << "/" << b << endl;
//
//		return 0;
//	}
//	pos = str.find("%");
//	if (pos != string::npos)
//	{
//		str.pop_back();
//		while (str.size() > 1 && str[str.size() - 1] == '0')
//			str.pop_back();
//
//		reverse(str.begin(), str.end());
//
//		cout << str << "%" << endl;
//
//		return 0;
//	}
//	while (str.size() > 1 && str[str.size() - 1] == '0')
//		str.pop_back();
//
//	reverse(str.begin(), str.end());
//
//	cout << str << endl;
//
//	return 0;
//}



//#include <iostream>
//#include <algorithm>
//#include <string>
//using namespace std;
//
//string s1[12] = { "another","one", "two", "three", "four", "five",
//				 "six", "seven", "eight", "nine" };
//string s2[12] = { "ten","eleven", "twelve", "thirteen", "fourteen", "fifteen",
//				 "sixteen", "seventeen", "eighteen", "nineteen", "twenty" };
//				 
//int a[22];
//string ret[22];
//int pos = 0;
//
//string str;
//
//bool cmp(string& x, string& y)
//{
//	return x + y < y + x;
//}
//
//int main()
//{
//	a[0] = 1;
//	for (int i = 1; i <= 20; i++)
//	{
//		a[i] = i;
//	}
//	
//	getline(cin, str);
//	int cnt = 0;
//	for (int i = 0; i <= 20; i++)
//	{
//		if (i <= 10)
//		{
//			if (str.find(s1[i]) != string::npos && str.find(s2[i]) != str.find(s1[i]))
//			{
//				cnt++;
//				if (a[i] * a[i] % 100 < 10)
//				{
//					ret[++pos] = "0" + to_string(a[i] * a[i] % 100);
//				}
//				else
//				{
//					ret[++pos] = to_string(a[i] * a[i] % 100);
//
//				}
//			}
//		}
//		else
//		{
//			if (str.find(s2[i - 10]) != string::npos)
//			{
//				cnt++;
				//if (a[i] * a[i] % 100 < 10)
				//{
				//	ret[++pos] = "0" + to_string(a[i] * a[i] % 100);
				//}
				//else
				//{
				//	ret[++pos] = to_string(a[i] * a[i] % 100);

				//}
//			}
//		}
//	}
//
	//if (cnt == 0)
	//{
	//	cout << 0 << endl;
	//	return 0;
	//}

	//sort(ret + 1, ret + 1 + pos, cmp);

	//string ans;
	//for (int i = 1; i <= pos; i++)
	//{
	//	ans += ret[i];
	//}

	//while (ans.size() > 1 && ans[0] == '0')
	//{
	//	ans.erase(0, 1);
	//}

	//cout << ans << endl;

	//return 0;
//}



//#include <iostream>
//#include <algorithm>
//#include <string>
//using namespace std;
//
//string s[30] = { "another","one", "two", "three", "four", "five",
//				 "six", "seven", "eight", "nine", "ten", 
//				 "eleven", "twelve", "thirteen", "fourteen", "fifteen",
//				 "sixteen", "seventeen", "eighteen", "nineteen", "twenty",
//				 "a", "both", "first", "second", "third" };
//
//int a[30];
//string ret[30];
//int pos = 0;
//
//string str;
//
//bool cmp(string& x, string& y)
//{
//	return x + y < y + x;
//}
//
//int main()
//{
//	a[0] = 1;
//	for (int i = 1; i <= 20; i++)
//	{
//		a[i] = i;
//	}
//	a[21] = 1;
//	a[22] = 2;
//	a[23] = 1;
//	a[24] = 2;
//	a[25] = 3;
//
//
//	getline(cin, str);
//
//	int len = str.size();
//	string num;
//	int cnt = 0;
//	for (int i = 0; i <= len; i++)
//	{
//		if (i < len && str[i] != ' ')
//		{
//			num += str[i];
//		}
//		else
//		{
//			for (int j = 0; j <= 25; j++)
//			{
//				if (num == s[j])
//				{
//					cnt++;
//					//cout << num  << " " << s[j] << " " << a[j] << endl;
//					if (a[j] * a[j] % 100 < 10)
//					{
//						ret[++pos] = "0" + to_string(a[j] * a[j] % 100);
//					}
//					else
//					{
//						ret[++pos] = to_string(a[j] * a[j] % 100);
//					}
//
//					break;
//				}
//			}
//			num = "";
//		}
//	}
//
//	if (cnt == 0)
//	{
//		cout << 0 << endl;
//		return 0;
//	}
//
//	sort(ret + 1, ret + 1 + pos, cmp);
//
//	string ans;
//	for (int i = 1; i <= pos; i++)
//	{
//		ans += ret[i];
//	}
//
//	while (ans.size() > 1 && ans[0] == '0')
//	{
//		ans.erase(0, 1);
//	}
//
//	cout << ans << endl;
//
//	return 0;
//
//}


//#include <iostream>
//#include <string>
//using namespace std;
//
//string a, b;
//
//int main()
//{
//	cin >> a >> b;
//	int len1 = a.size();
//	int len2 = b.size();
//	int ret1 = 1;
//	int ret2 = 1;
//	for (int i = 0; i < len1; i++)
//	{
//		ret1 *= (a[i] - 'A') + 1;
//		ret1 %= 47;
//	}
//	for (int i = 0; i < len2; i++)
//	{
//		ret2 *= (b[i] - 'A') + 1;
//		ret2 %= 47;
//	}
//
//	if (ret1 == ret2)
//		cout << "GO" << endl;
//	else
//		cout << "STAY" << endl;
//
//	return 0;
//}


//#include <iostream>
//using namespace std;
//
//long long n, m;
//
//int main()
//{
//	cin >> n >> m;
//	long long ret1 = 0;
//	long long ret2 = 0;
//	for (int i = 1; i <= min(n, m); i++)
//	{
//		ret1 += (n - i + 1) * (m - i + 1);
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			ret2 += (n - i + 1) * (m - j + 1);
//		}
//	}
//
//	cout << ret1 << " " << ret2 - ret1 << endl;
//
//	return 0;
//}


//
//#include <iostream>
//using namespace std;
//
//typedef long long ll;
//
//const int N = 5e3 + 10;
//const int MOD = 1e9 + 7;
//
//int n;
//ll cnt[N] = { 0 };
//
//int main()
//{
//	cin >> n;
//	int mx = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		int x;
//		cin >> x;
//		mx = max(mx, x);
//		cnt[x]++;
//	}
//
//	ll ret = 0;
//
//	for (int i = 1; i <= mx; i++)
//	{
//		if (cnt[i] < 2)
//			continue;
//
//		ll tmp = (cnt[i] * (cnt[i] - 1)) / 2;
//		ll num = 0;
//		for (int j = 1; 2 * j <= i; j++)
//		{
//			if (cnt[j] > 0 && cnt[i - j] > 0)
//			{
//				if (i - j == j)
//				{
//					num += (cnt[j] * (cnt[j] - 1)) / 2;
//				}
//				else
//				{
//					num += cnt[j] * cnt[i - j];
//				}
//				num %= MOD;
//			}
//		}
//
//		ret += tmp * num;
//		ret %= MOD;
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}



//#include <iostream>
//#include <vector>
//using namespace std;
//
//vector<int> path;
//vector<int> ans[500000];
//int n;
//int ret = 0;
//
//void dfs(int x, int sum)
//{
//	if (x == 10)
//	{
//		if (sum == n)
//		{
//			ret++;
//			for (auto ch : path)
//			{
//				ans[ret].push_back(ch);
//			}
//		}
//		return ;
//	}
//
//	for (int i = 1; i <= 3; i++)
//	{
//		path.push_back(i);
//		dfs(x + 1, sum + i);
//		path.pop_back();
//	}
//
//}
//
//int main()
//{
//	cin >> n;
//	dfs(0, 0);
//
//	cout << ret << endl;
//	for (int i = 1; i <= ret; i++)
//	{
//		for (auto ch : ans[i])
//		{
//			cout << ch << " ";
//		}
//		cout << endl;
//	}
//
//	return 0;
//}


#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

vector<int> edges[N];
bool st[N] = { 0 };

int n, m;

void dfs(int x)
{
	st[x] = 1;
	cout << x << " ";

	for (auto ch : edges[x])
	{
		if (st[ch] == 0)
		{
			dfs(ch);
		}
	}
}

void bfs()
{
	memset(st, 0, sizeof(st));
	queue<int> q;
	q.push(1);
	st[1] = 1;

	while (q.size())
	{
		int t = q.front();
		cout << t << " ";
		q.pop();


		for (auto ch : edges[t])
		{
			if (st[ch] == 0)
			{
				q.push(ch);
				st[ch] = 1;
			}
		}
	}

}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		edges[x].push_back(y);
	}

	for (int i = 1; i <= n; i++)
	{
		sort(edges[i].begin(), edges[i].end());
	}

	dfs(1);
	cout << endl;
	bfs();

	return 0;
}
